1. Field of the Invention
This invention relates in general to database management systems performed by computers, and in particular, to the optimization of queries that include left outer joins.
2. Description of Related Art
Since its introduction, XML, the eXtended Markup Language, has quickly emerged as a universal format for publishing and exchanging data over the World Wide Web. However, problems still exist in publishing data from relational databases as XML documents.
In the business-to-business e-commerce area, there is a widely recognized need to create XML documents by combining one or more relational tables, e.g., by creating an XML purchase order by joining a customer with information drawn from other tables. A relational join is a well-known operation that combines information from two base tables by creating pairs of matching rows.
Inner joins discard rows without any matches, while outer joins preserve all information from one or both of its arguments. Outer joins can be further categorized into left, right (single-sided), or full (two-sided) outerjoin, depending on which side needs to be preserved.
Outer joins are especially useful for exporting data from relational databases to XML documents. However, there are performance costs associated with performing such outer joins. Thus, there is a need in the art for improved techniques of performing outer joins, and especially for optimization methods for outer joins.
To overcome the limitations in the prior art described above, and to overcome other limitations that will become apparent upon reading and understanding the present specification, the present invention discloses a method, apparatus, and article of manufacture for optimizing left outer join queries. A determination is made whether any column from a right quantifier of a left outer join query is projected out of the query. If not, then all predicates in an ON clause are removed from the left outer join query, the right quantifier is removed from the left outer join query, and the left outer join query is converted to a simple select query.
A number of steps are performed to determine whether any of the columns quantified by the right quantifier participate in a projection list of the query. A set of equivalence class columns is computed for the query, wherein the equivalence classes are derived from equi-join predicates in the query. A set of columns quantified by the right quantifier across the computed set of equivalence classes is computed. A determination is made whether a subset of the set of columns form a key for the right quantifier. If the right quantifier columns are not projected out of the query, then the optimization may be performed.